package com.le.high.class4;

import org.junit.Test;

/**
 * 给定一个字符串str，返回把str全部切成回文子串的最小分割数。
 * 【举例】
 * str="ABA"。 不需要切割，str本身就是回文串，所以返回0。
 * str="ACDCDCDAD"。 最少需要切2次变成3个回文子串，比如"A"、"CDCDC"和"DAD"，所以返回2
 * <p>
 * 从左往右尝试模型
 */
public class Problem04_PalindromeMinCut {

    public static int minCut1(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] s1 = str.toCharArray();
        boolean[][] dp = getDp(s1);
        return process(str.toCharArray(), 0, dp) - 1;
    }


    public static int process(char[] chs, int index, boolean[][] dp) {
        if (index == chs.length) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for (int end = index; end < chs.length; end++) {
            // end...index 是否是回文串
//            if (isValid(chs, index, end)) {
//                res = Math.min(res, 1 + process(chs, end + 1, dp));
//            }
            if (dp[index][end]) {
                res = Math.min(res, 1 + process(chs, end + 1, dp));
            }
        }
        return res;
    }

    public static boolean[][] getDp(char[] s1) {
        boolean[][] dp = new boolean[s1.length][s1.length];
        for (int i = 0; i < s1.length; i++) {
            dp[i][i] = true;
        }
        for (int i = 0; i < dp.length - 1; i++) {
            dp[i][i + 1] = s1[i] == s1[i + 1] ? true : false;
        }
        for (int i = dp.length - 3; i > -1; i--) {
            for (int j = i + 2; j < dp[0].length; j++) {
                dp[i][j] = s1[i] == s1[j] ? dp[i + 1][j - 1] : false;
            }
        }
        return dp;
    }

    public static boolean isValid(char[] ch, int left, int right) {
        while (left <= right) {
            if (ch[left] == ch[right]) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }

    public static int minCut2(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] chas = str.toCharArray();
        int len = chas.length;
        int[] dp = new int[len + 1];
        dp[len] = -1;
        boolean[][] p = new boolean[len][len];
        for (int i = len - 1; i >= 0; i--) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = i; j < len; j++) {
                if (chas[i] == chas[j] && (j - i < 2 || p[i + 1][j - 1])) {
                    p[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0];
    }

    // for test
    public static String getRandomStringOnlyAToD(int len) {
        int range = 'D' - 'A' + 1;
        char[] charArr = new char[(int) (Math.random() * (len + 1))];
        for (int i = 0; i != charArr.length; i++) {
            charArr[i] = (char) ((int) (Math.random() * range) + 'A');
        }
        return String.valueOf(charArr);
    }

    @Test
    public void test() {
        int maxLen = 10;
        int testTimes = 20;
        String str = null;
        for (int i = 0; i != testTimes; i++) {
            str = getRandomStringOnlyAToD(maxLen);
            System.out.print("\"" + str + "\"" + " : \n");
            System.out.println(minCut1(str));
            System.out.println(minCut2(str));

        }
    }
}
